package 力扣;

import org.hamcrest.core.Is;
import org.w3c.dom.ls.LSException;
import sun.security.util.Length;

import javax.sound.midi.Soundbank;
import java.time.Year;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author yyq
 * @create 2022-05-31 10:24
 */
public class leetcode491 {
    public static void main(String[] args) {
        leetcode491 l=new leetcode491();
        List<List<Integer>> subsequences = l.findSubsequences(new int[]{1,2,1,1,3 });
        System.out.println(subsequences);
    }

    List<Integer> list=new ArrayList<>();
    List<List<Integer>> lists=new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
       int startIndex = 0;
       backTracking(nums,list,lists,startIndex);
       return lists;
    }

    private void backTracking(int[] nums, List<Integer> list, List<List<Integer>> lists, int startIndex) {
        if(list.size()>1)
            lists.add(new ArrayList<>(list));

        for (int i = startIndex; i < nums.length; i++) {


                // 剪支 出现 4 2 的情况
                if(list.size()>1&&list.get(list.size()-1)>nums[i])
                    continue;
                // 剪支 出现重复数据
                int flag = 0;
                for (int j = startIndex;j<i;j++){
                    if(nums[j] == nums[i]) {
                        flag=1;
                        break;
                    }
                }
                if(flag==1) continue;


            list.add(nums[i]);
            backTracking(nums,list,lists,i+1);
            list.remove(list.size()-1);
        }
    }
}
